//Given a linked list, swap every two adjacent nodes and return its head.
//For example, Given 1->2->3->4, you should return the list as 2->1->4->3.
//Your algorithm should use only constant space.You may not modify the values in the list, only nodes
//itself can be changed.


#include<iostream>
using namespace std;

template<typename T>
struct SingleList{
	T _value;
	SingleList<T> *_next;
	SingleList(T value)
		:_value(value),
		_next(NULL)
	{}
};


template<typename T>
class Solution{
public:

	SingleList<T> *Swap(SingleList<T> *head)
	{
		if (head == NULL)
		{
			cout << "NULL";
			return head;
		}
		SingleList<T> *cur = head;
		SingleList<T> *prev = cur;
		int index = 2;
		while (cur->_next != NULL)
		{
			
			if (index % 2 == 0)
			{	
				index++;
				prev = cur;
				cur = cur->_next;
				swap(prev->_value, cur->_value);
			}
			else
			{
				index++;
				cur = cur->_next;
			}
		}	
		return head;
	}

	void Display(SingleList<T> *&head)
	{
		if (head == NULL)
		{
			cout << "NULL";
			return;
		}
		SingleList<T> *cur = head;
		while (cur)
		{
			cout << cur->_value << "->";
			cur = cur->_next;
		}
		cout << "NULL" << endl;
	}
};
int main()
{
	SingleList<int> *head = new SingleList<int>(1);
	SingleList<int> *list1 = new SingleList<int>(2);
	SingleList<int> *list2 = new SingleList<int>(3);
	SingleList<int> *list3 = new SingleList<int>(4);
	SingleList<int> *list4 = new SingleList<int>(5);
	SingleList<int> *list5 = new SingleList<int>(6);
	head->_next = list1;
	list1->_next = list2;
	list2->_next = list3;
	list3->_next = list4;
	list4->_next = list5;
	Solution<int> s;
	SingleList<int> *ret = s.Swap(head);
	s.Display(ret);
	return 0;
}